/*
 * Proposed design and a working prototype for Dart's core collections with
 * immutable types.
 *
 * FAQ
 *
 * Why?
 *   Many experienced developers agree on the benefits of immutability in
 *   certain data-structures. For languages that don't provide it in the core
 *   libraries the community had to develop 3rd-party solutions. For example,
 *   for Java there exist numerous frameworks that provide immutable data-
 *   structures, such as Protocol Buffers, Guava and Apache Commons. With
 *   collections being one of the most important data-structures it is therefore
 *   important to have immutable collections.
 * Why have immutable collections in the core libs? Is 3rd-party not enough?
 *   No, 3rd-party is not enough. A mutable data-type should extend (i.e.
 *   inherit from) its immutable counterpart. Both Guava and Apache Commons had
 *   to compromise. Guava chose compatibility with java.util over clean API, by
 *   having immutable types extend mutable, e.g. ImmutableList implements
 *   java.util.List but throws runtime exceptions in all the mutator methods.
 *   Apache Commons chose to have a clean API but at the expense of
 *   incompatibility with Java's standard libraries, e.g. UnmodifiableList is
 *   not assignable to java.util.List. Therefore most of the popular libraries
 *   just use standard collections at the expense of having to create defensive
 *   copies, wasting CPU and memory in the process, or throwing runtime
 *   exceptions for errors that should be caught by the compiler.
 * Some programmers coming from imperative languages grew comfortable with
 * mutable-only collections. Won't this confuse them?
 *   The proposed design takes this into account by: a). reserving the common
 *   collection names for mutable classes and b). preserving the original API as
 *   much as practical. So programmers who don't care or don't know about
 *   immutable collections will need minimal or no adjustment.
 *
 * Design
 *
 * Each collection kind has an immutable and a mutable version. The mutable
 * versions extend their immutable counterparts. The proposed naming convention
 * is to use common names for mutable versions, e.g. List, Set, Map. Immutable
 * versions will be prefixed with Readable, e.g ReadableList, ReadableSet,
 * ReadableMap. Here's the class hierarchy:
 *
 * (a picture's worth 1k words: http://goo.gl/MlQkL)
 *
 * Iterables:
 *   Iterable<E>
 *   Collection<E> extends Iterable<E>
 *   ReadableList<E> extends Collection<E>
 *   List<E> extends ReadableList<E>
 *   ReadableSet<E> extends Collection<E>
 *   Set<E> extends ReadableSet<E>
 *   HashSet<E extends Hashable> extends Set<E>
 *   Queue<E> extends Collection<E>
 *
 * Maps:
 *   ReadableMap<K, V>
 *   Map<K, V> extends ReadableMap<K, V>
 *   HashMap<K extends Hashable, V> extends Map<K, V>
 *   LinkedHashMap<K extends Hashable, V> extends HashMap<K, V>
 *
 * Because Iterator, Iterable and Collection are already immutable, no change is
 * necessary, they are good to go. An immutable Queue would not be very useful,
 * so it stays unchanged too.
 *
 * Prototype
 *
 * Partially to avoid a name conflict with the existing Dart collections, and
 * partially due to my laziness this prototype uses a different naming
 * convention. Immutable types are prefixed with "Read", e.g. ReadList. Mutable
 * types are prefixed with "Write", e.g. WriteLinkedHashMap.
 *
 * The point of this prototype is only to demonstrate the API, which is why the
 * implementations are backed by current Dart collections. No new functionality
 * is proposed. The existing functions are simply reorganized, getters go into
 * immutable classes, mutators go into mutable classes.
 */

// TODO: Should we override Collection.filter((bool f(E e)) for each type?

interface ReadList<E> extends Collection<E> factory ReadListFactory {
  ReadList.from(Iterable<E> other);
  E operator [](int index);
  int indexOf(E element, [int start]);
  int lastIndexOf(E element, [int start]);
  E last();
  ReadList<E> getRange(int start, int length);
}

interface WriteList<E> extends ReadList<E> factory WriteListFactory {
  WriteList.from(Iterable<E> other);
  WriteList([int length]);
  void operator []=(int index, E value);
  void set length(int newLength);
  void add(E value);
  void addLast(E value);
  void addAll(Collection<E> collection);
  void sort(int compare(E a, E b));
  void clear();
  E removeLast();
  WriteList<E> getRange(int start, int length);
  
  // TODO: Should these be spun off to an ExtendableList?
  void setRange(int start, int length, ReadList<E> from, [int startFrom]);
  void removeRange(int start, int length);
  void insertRange(int start, int length, [E initialValue]);
}

interface ReadSet<E> extends Collection<E> factory ReadSetFactory {
  ReadSet.from(Iterable<E> other);
  bool contains(E value);
  bool isSubsetOf(Collection<E> collection);
  bool containsAll(Collection<E> collection);
  ReadSet<E> intersection(Collection<E> other);
}

interface WriteSet<E> extends ReadSet<E> factory WriteSetFactory {
  WriteSet.from(Iterable<E> other);
  WriteSet();
  WriteSet<E> intersection(Collection<E> other);
  void add(E value);
  bool remove(E value);
  void addAll(Collection<E> collection);
  void removeAll(Collection<E> collection);
  void clear();
}

interface WriteHashSet<E extends Hashable> extends WriteSet<E>
    factory WriteHashSetFactory {
  WriteHashSet.from(Iterable<E> other);
  WriteHashSet();
  WriteHashSet<E> intersection(Collection<E> other);
}

interface ReadMap<K, V> factory ReadMapFactory {
  ReadMap.from(ReadMap<K, V> other);
  bool containsValue(V value);
  bool containsKey(K key);
  V operator [](K key);
  void forEach(void f(K key, V value));
  Collection<K> getKeys();
  Collection<V> getValues();
  int get length();
  bool isEmpty();
}

interface WriteMap<K, V> extends ReadMap<K, V> factory WriteMapFactory {
  WriteMap();
  WriteMap.from(ReadMap<K, V> other);
  void operator []=(K key, V value);
  V putIfAbsent(K key, V ifAbsent());
  V remove(K key);
  void clear();
}

interface WriteHashMap<K extends Hashable, V> extends WriteMap<K, V>
    factory WriteHashMapFactory {
  WriteHashMap();
  WriteHashMap.from(ReadMap<K, V> other);
}

interface WriteLinkedHashMap<K extends Hashable, V> extends WriteHashMap<K, V>
    factory WriteLinkedHashMapFactory {
  WriteLinkedHashMap();
  WriteLinkedHashMap.from(ReadMap<K, V> other);
}


// Impls

class ReadListFactory {
  factory ReadList<E>.from(Iterable<E> other) {
    return new ReadListImplementation(new List.from(other));
  }
}

class ReadListImplementation<E> implements ReadList<E> {
  ReadListImplementation(List<E> this._array);
  List<E> _array;

  E operator [](int index) {
    return _array[index];
  }
  
  int indexOf(E element, [int start = 0]) {
    return _array.indexOf(element, start);
  }
  
  int lastIndexOf(E element, [int start = 0]) {
    return _array.lastIndexOf(element, start);
  }
  
  E last() {
    return _array.last();
  }
  
  ReadList<E> getRange(int start, int length) {
    List<E> range = _array.getRange(start, length);
    return new ReadListImplementation(range);
  }

  void forEach(void f(E element)) {
    _array.forEach(f);
  }

  Collection<E> filter(bool f(E element)) {
    return _array.filter(f);
  }

  bool every(bool f(E element)) {
    return _array.every(f);
  }

  bool some(bool f(E element)) {
    return _array.some(f);
  }

  bool isEmpty() {
    return _array.isEmpty();
  }

  int get length() {
    return _array.length;
  }
  
  Iterator<E> iterator() {
    return _array.iterator();
  }
}

class WriteListFactory {
  factory WriteList<E>.from(Iterable<E> other) {
    List<E> backingList = new List<E>();
    for (E e in other) {
      backingList.add(e);
    }
    return new WriteListImplementation(backingList);
  }

  factory WriteList<E>([int length = null]) {
    return new WriteListImplementation(new List(length));
  }
}

class WriteListImplementation<E> extends ReadListImplementation<E>
    implements WriteList<E> {
  WriteListImplementation(List<E> _array) : super(_array);

  void operator []=(int index, E value) {
    _array[index] = value;
  }

  void set length(int newLength) {
    _array.length = newLength;
  }
  
  void add(E value) {
    _array.add(value);
  }
  
  void addLast(E value) {
    _array.addLast(value);
  }
  
  void addAll(Collection<E> collection) {
    _array.addAll(collection);
  }
  
  void sort(int compare(E a, E b)) {
    _array.sort(compare);
  }
  
  void clear() {
    _array.clear();
  }
  
  E removeLast() {
    return _array.removeLast();
  }
  
  WriteList<E> getRange(int start, int length) {
    return new WriteListImplementation(_array.getRange(start, length));
  }

  void setRange(int start, int length, ReadList<E> from, [int startFrom = 0]) {
    List<E> fromList = new List.from(from);
    _array.setRange(start, length, fromList, startFrom);
  }

  void removeRange(int start, int length) {
    _array.removeRange(start, length);
  }
  
  void insertRange(int start, int length, [E initialValue = null]) {
    _array.insertRange(start, length, initialValue);
  }
}

class ReadSetFactory {
  factory ReadSet<E>.from(Iterable<E> other) {
    return new ReadSetImplementation(new HashSet.from(other));
  }
}

class ReadSetImplementation<E extends Hashable> implements ReadSet<E> {
  ReadSetImplementation(HashSet<E> this._set);
  HashSet<E> _set;

  bool contains(E value) {
    return _set.contains(value);
  }
  
  bool isSubsetOf(Collection<E> collection) {
    return _set.isSubsetOf(collection);
  }
  
  bool containsAll(Collection<E> collection) {
    return _set.containsAll(collection);
  }
  
  ReadSet<E> intersection(Collection<E> other) {
    return new ReadSetImplementation(_set.intersection(other));
  }

  void forEach(void f(E element)) {
    _set.forEach(f);
  }

  Collection<E> filter(bool f(E element)) {
    return _set.filter(f);
  }

  bool every(bool f(E element)) {
    return _set.every(f);
  }

  bool some(bool f(E element)) {
    return _set.some(f);
  }

  bool isEmpty() {
    return _set.isEmpty();
  }

  int get length() {
    return _set.length;
  }
  
  Iterator<E> iterator() {
    return _set.iterator();
  }
}

class WriteSetFactory {
  factory WriteSet<E>.from(Iterable<E> other) {
    return new WriteSetImplementation(new HashSet.from(other));
  }

  factory WriteSet<E>() {
    return new WriteSetImplementation(new HashSet());
  }
}

class WriteSetImplementation<E extends Hashable>
    extends ReadSetImplementation<E>
    implements WriteSet<E> {
  WriteSetImplementation(Iterable<E> other) : super(other);
  
  WriteSet<E> intersection(Collection<E> other) {
    return new WriteSetImplementation(_set.intersection(other));
  }

  void add(E value) {
    _set.add(value);
  }
  
  bool remove(E value) {
    return _set.remove(value);
  }
  
  void addAll(Collection<E> collection) {
    _set.addAll(collection);
  }
  
  void removeAll(Collection<E> collection) {
    _set.removeAll(collection);
  }
  
  void clear() {
    _set.clear();
  }
}

class WriteHashSetFactory {
  factory WriteHashSet<E>.from(Iterable<E> other) {
    return new WriteHashSetImplementation(new HashSet.from(other));
  }
  
  factory WriteHashSet<E>() {
    return new WriteHashSetImplementation(new HashSet());
  }
}

class WriteHashSetImplementation<E extends Hashable>
    extends WriteSetImplementation<E>
    implements WriteHashSet<E> {
  WriteHashSetImplementation(Iterable<E> other) : super(other);

  WriteHashSet<E> intersection(Collection<E> other) {
    return new WriteHashSetImplementation(super.intersection(other));
  }
}

class ReadMapFactory {
  factory ReadMap<K, V>.from([ReadMap<K, V> other = null]) {
    return new ReadMapImplementation(other);
  }
}

class ReadMapImplementation<K, V> implements ReadMap<K, V> {
  ReadMapImplementation([ReadMap<K, V> other = null]) {
    var map = new Map();
    if (other != null) {
      other.forEach((K key, V value) {
        map[key] = value;
      });
    }
    this._map = map;
  }

  ReadMapImplementation.linked([ReadMap<K, V> other = null]) {
    var map = new LinkedHashMap();
    if (other != null) {
      other.forEach((K key, V value) {
        map[key] = value;
      });
    }
    this._map = map;
  }
  
  Map<K, V> _map;
  
  bool containsValue(V value) {
    return _map.containsValue(value);
  }
  
  bool containsKey(K key) {
    return _map.containsKey(key);
  }
  
  V operator [](K key) {
    return _map[key];
  }
  
  void forEach(void f(K key, V value)) {
    _map.forEach(f);
  }
  
  Collection<K> getKeys() {
    return _map.getKeys();
  }
  
  Collection<V> getValues() {
    return _map.getValues();
  }
  
  int get length() {
    return _map.length;
  }
  
  bool isEmpty() {
    return _map.isEmpty();
  }
}

class WriteMapFactory {
  factory WriteMap<K, V>() {
    return new WriteMapImplementation();
  }

  factory WriteMap<K, V>.from(ReadMap<K, V> other) {
    return new WriteMapImplementation(other);
  }
}

class WriteHashMapFactory {
  factory WriteHashMap<K, V>() {
    return new WriteMapImplementation();
  }
  
  factory WriteHashMap<K, V>.from(ReadMap<K, V> other) {
    return new WriteMapImplementation(other);
  }
}

class WriteLinkedHashMapFactory {
  factory WriteLinkedHashMap<K, V>() {
    return new WriteMapImplementation.linked();
  }
  
  factory WriteLinkedHashMap<K, V>.from(ReadMap<K, V> other) {
    return new WriteMapImplementation.linked(other);
  }
}

class WriteMapImplementation<K, V> extends ReadMapImplementation<K, V>
    implements WriteMap<K, V> {
  WriteMapImplementation([ReadMap<K, V> other = null]) : super(other);
  WriteMapImplementation.linked([ReadMap<K, V> other = null]) :
    super.linked(other);
  
  void operator []=(K key, V value) {
    _map[key] = value;
  }

  V putIfAbsent(K key, V ifAbsent()) {
    return _map.putIfAbsent(key, ifAbsent);
  }
  
  V remove(K key) {
    return _map.remove(key);
  }
  
  void clear() {
    _map.clear();
  }
}
